package 动态规划.背包And分组And切割问题系列;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;

import org.junit.Test;
/**
 * https://www.acwing.com/problem/content/2/
 * 题目  链接
 * @author I adore you
 */
public class Acwing01背包问题 {
	public static void main(String []args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int V = sc.nextInt();
		int arr [][] = new int [N][2];
		for(int  i = 0;i < N;i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		System.out.println(solution(arr,0,V,N));
		System.out.println(solutionDP(arr,N,V));
		System.out.println(dp(arr,V));
		System.out.println(solution(arr,0,V,N));
		System.out.println(new Acwing01背包问题().solution(arr,V));

		output();
		sc.close();
	}
	static void output() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		String  line[] = in.readLine().split(" ");
		int N = Integer.parseInt(line[0]);
		int V = Integer.parseInt(line[1]);
		int arr [][] = new int [N][2];
		for(int i = 0;i < N;i++) {
			line = in.readLine().split(" ");
			arr[i][0] = Integer.parseInt(line[0]);
			arr[i][1] = Integer.parseInt(line[1]);
		}
		/**
		 * 这里 为啥 还用 输出  一个 换行 呢 不就是 单行  答案  就不需要 换行对吧
		 * 还有 一个 问题 就是 
		 * in  和 out 都不能 处理  int 数据
		 * 这就比较 烦 
		 * 需要转换 为 String  进行输入 输出
		 * 
		 */
//		out.write(solutionDP(arr,N,V) + "\n");
		out.write(solutionDP(arr,N,V));
		out.flush();
		out.close();
		//System.out.println(solutionDP(arr,N,V)); 这跟 上面的 效率 差不多的 
	}
	static int solution(int arr[][],int index,int rest,int len) {
		if(rest == 0 || index == len)
			return 0;
		int ans = 0;
		for(int i = index; i < len ;i++) {
			if(rest - arr[i][0] >= 0) {
				ans = Math.max(ans, solution(arr,i + 1,rest - arr[i][0],len ) + arr[i][1]);
			}
		}
		return ans;
	}


	// 上面 这种多叉树 递归 ，改成的 dp
	public static int dp(int nums[][],int rest){
		int len = nums.length;
		int dp[][] = new int[len + 1][rest + 1];
		for(int index = len - 1;index >= 0;index--){
			for(int x = 1;x <= rest;x++){
				int ans = 0;
				for(int i = index;i < len;i++){
					if(x - nums[i][0] >= 0){
						ans = Math.max(ans,dp[i + 1][x - nums[i][0]] + nums[i][1]);
					}
				}
				dp[index][x] = ans;
			}
		}
		return dp[0][rest];
	}


	// 二叉树 递归 改的 dp


	static int solutionDP(int arr[][],int N,int V) {
		int  dp [][]  = new int [N + 1][V + 1];
		for(int i = N - 1;i >= 0;i--) {
			for(int j = 1;j <= V ;j++) {
//				ans = Math.max(a, b);
				dp [i][j] = dp[i +1][j];
				if(j >= arr[i][0])
					dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - arr[i][0]] + arr[i][1]);
			}
		}
		return dp[0][V];
	}
	
	
	
	
	
	public static int process1(int index,int choice[],int rest,int value[]) {
		if(rest == 0 || index == choice.length)
			return 0;
		int ans = 0;
		if(rest >= choice[index])
			ans = process1(index + 1,choice,rest - choice[index],value) + value[index];
		ans = Math.max(ans,process1(index + 1,choice,rest,value));
		return ans;
	}
	
	
	// 
	public static int process2(int index,int rest,int choice[],int value[]) {
		if(rest == 0)
			return 0;
		int ans = 0;
		for(int i = index;i < choice.length;i++) {
			if(rest >= choice[i])
				ans = Math.max(ans, process2(i + 1,rest - choice[i],choice,value) + value[i]);
		}
		return ans;
	}

	/*
	2023/5/27
	顺推， 逆推，全部都写一遍， 注意思考一下 y = f（i， rest） 的含义
	 */

	// f(index,rest) 表示的是， 从index ~ end 背包容量 为 rest 的时候， 挑选商品能获取的最大价值
	public int function01(int index,int goods[][],int rest){
		// basecase
		if(index == goods.length || rest == 0){ // 添加 这个 rest == 0  basecase ，可以减少一些不必要的递归！
			return 0;
		}
		// no
		int ans = function01(index + 1,goods,rest);
		//yes , 这种选择是 有限制的， 背包的容量不能 为 负数
		if(rest - goods[index][0] >= 0){
			ans = Math.max(ans,function01(index + 1,goods,rest - goods[index][0]) + goods[index][1]);
		}
		return ans;
	}
	// 正序， f（index， rest） 表示的是 ，从 start ~ index ，背包容量为 rest 的时候 能获得的最大价值
	public int function(int index,int [][]goods,int rest,Integer dp[][]){
		if(index == -1 || rest == 0){
			return 0;
		}
		if(dp[index][rest] != null){
			return dp[index][rest];
		}
		// no
		int ans = function(index - 1,goods,rest,dp);
		// yes need a limit
		if(rest - goods[index][0] >= 0){
			ans = Math.max(ans,function(index - 1,goods,rest - goods[index][0],dp) + goods[index][1]);
		}
		return dp[index][rest] = ans;
	}

	public int solution(int nums[][],int v){
		int len = nums.length;

		Integer dp[][] = new Integer[len + 1][v + 1];

		function(len - 1,nums,v,dp);
		return dp[len - 1][v];
	}


	@Test
	public void test() {
		int choice[] = {1,2,3,4};
		int value [] = {2,4,4,5};
		System.out.println(process1(0,choice,5,value));
		System.out.println(process2(0,5,choice,value));
		System.out.println();
	}
	
	
}
